\documentclass[a4paper,10pt]{article}
\usepackage{lipsum}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}
\usepackage[portuguese]{babel}

%opening
\title{Algoritmos de {\it Branch and Bound}}
\author{Ítalo Quirino Brilhante}

% se não quiser que apareça a data da compilação use:
\date{}

\begin{document}

\maketitle

\begin{abstract}
Texto sobre algoritmos de {\it branch and bound} para teste do \LaTeX.

\end{abstract}

\section{Introdução}

Um algoritmo é uma sequência finita de instruções bem definidas e não ambíguas. Cada uma destas instruções pode ser executada em um período de tempo finito e com uma quantidade de esforço finita.

{\it Branch and bound} é uma técnica de otimização que faz uso de uma árvore de enumeração objetivando a resolução de um problema. Os nós da árvore representam subproblemas do problema observado e os ramos representam restrições a serem examinadas \cite{lobato}.


Um algoritmo de {\it branch and bound} realiza três processos:


\begin{itemize}
\item Dividir o problema em subproblemas menos complexos;
\item Calcular limites superiores e inferiores para o valor ótimo do subproblema;
\item Podar ramos da árvore que não necessitam ser visitados.
\end{itemize}

A divisão do problema tem como objetivo gerar subproblemas de complexidade reduzida em relação ao problema original, de maneira que encontrando a solução dos subproblemas, é encontrada uma solução para o problema original. São calculados os limites superiores e inferiores, de modo a avaliar a possibilidade de encontrar uma melhor solução no ramo de cada subproblema. Os ramos onde identifica-se que os nós relacionados a ele não geram soluções melhores que a atual são podados (cortados).

\section{Algoritmos de Branch and Bound}

\subsection{Descrição}

\newtheorem{teo}{Teorema}

\begin{teo}
Dizemos que Ps é um subproblema de um problema P se Ps tem a mesma função objetivo e se o seu conjunto viável está contido no conjunto viável de P.
\end{teo}

Cada nó da árvore representa um problema, sendo que o nó raiz é relativo ao problema principal e cada aresta representa a inclusão de uma nova restrição. Deste modo, cada nó herdará o problema do nó antecessor, com uma restrição a mais.

Um algoritmo de {\it branch and bound} mantém a melhor solução {\it s} conhecida para o problema, bem como os problemas ainda não visitados, que inicia contendo somente o problema principal. Enquanto houver problemas candidatos, visita-se um problema {\it P} e o remove do conjunto. Seja {\it P'} o problema que se obtém a partir de {\it P}. Se a solução {\it s'} de {\it P'} satisfaz as restrições contidas nele, então {\it s'} consiste em uma solução ótima de {\it P} e a solução {\it s} passa a conter a solução {\it s'} \cite{lobato}.

\subsection{Avaliação}

Para a resolução de um problema, busca-se fazer uma relaxação do mesmo. Seja {\it P'} uma relaxação de um problema {\it P}.

\begin{teo}
Um problema de otimização {\it P'} é definido como uma relaxação do problema {\it P} se o conjunto de soluções viáveis de {\it P} é um subconjunto das soluções viáveis de {\it P'}.
\end{teo}


Deste modo, se {\it P'} não possui solução viável, então {\it P} também não possui. Também deve ser observado que se uma solução ótima de {\it P'} é solução viável de {\it P}, então ela é uma solução ótima de {\it P}.

\subsection{Exploração}

Ao realizar a análise de subproblemas, é necessário verificar quais devem ser examinados e quais devem ser descartados \cite{lobato}. Um subproblema {\it P} deve ser considerado explorado se:

\begin{itemize}
\item Houver uma forma de garantir que o conjunto das soluções viáveis de {\it P} não possui uma solução melhor do que a atual encontrada;
\item Uma solução ótima de {\it P} foi encontrada.
\end{itemize}


Nestes cenários, o subproblema {\it P} pode ser considerado resolvido e não é necessário examiná-lo detalhadamente com uma nova divisão. Sendo {\it P'} uma relaxação de {\it P}, existem três situações onde considera-se um subproblema {\it P} como explorado:

\begin{itemize}
\item Inviabilidade: {\it P'} não contém solução viável. Neste cenário, {\it P} também não possui solução viável e pode ser descartado;
\item Eliminação por Avaliação: Quando a solução ótima de {\it P'} tem um valor igual ou menos promissor ao da solução ótima obtida até o momento. Neste cenário, não é possível encontrar uma solução melhor que a atual, permitindo que o subproblema {\it P} seja descartado.
\item Otimalidade: A solução ótima de {\it P'} é solução viável de {\it P} e, portanto, é solução ótima de {\it P}.
\end{itemize}

\subsection{Exemplo}

Como exemplo para aplicação do algoritmo de {\it branch and bound}, podemos considerar o problema da atribuição. Este problema consiste em atribuir {\it n} pessoas e {\it n} tarefas de modo que o custo total da atribuição seja o menor possível. O problema é representado por uma matriz de custo {\it M}, ilustrada na Figura 1.

\begin{figure}[!h]
\centering
\includegraphics{branchandbound1}
\caption{Matriz de Custo M}
\end{figure}

As seguintes restrições devem ser observadas para este problema:

\begin{itemize}
\item Se um elemento de uma coluna for selecionado, nenhum outro elemento desta coluna deve ser selecionado;
\item A soma dos elementos selecionados deve ser a menor possível.
\end{itemize}


É preciso definir um limite inferior para as soluções \cite{koerich}. É possível observar que nenhuma solução para este problema terá um custo total menor que a soma dos menores elementos de cada linha, que neste caso, seria 2 + 3 + 1 + 4 = 10. Contudo, este não é o custo de nenhuma solução legítima (os elementos 3 e 1 estão na mesma coluna, não atendendo a uma das restrições), e sim apenas o limite inferior para o custo de uma solução legítima.

O resultado da expansão da árvore de busca é mostrado na Figura 2. O número acima de cada nó representa a ordem em que cada um dos nós foi gerado. Os campos internos de cada nó representam a tarefa selecionada por cada pessoa e o limite inferior de cada nó.

\begin{figure}[!h]
\centering
\includegraphics{branchandbound2}
\caption{Árvore de Busca - Níveis 0 e 1}
\end{figure}

Na Figura 2, o limite inferior continua a ser calculado considerando a seleção de uma determinada tarefa de uma coluna e somando-se aos menores elementos de cada coluna. Todavia, não é permitido considerar como menor número um valor que já tenha sido selecionado na primeira linha. Um exemplo disto ocorre no nó 4, onde a soma não consiste em 8 + 3 + 1 + 4 e sim 8 + 3 + 1 + 6, pois o número 4, presente na quarta linha e na quarta coluna, não pode ser selecionado, pois o número 8 pertence à quarta coluna e esta já foi utilizada.

Há 4 nós promissores. É preciso selecionar o mais promissor. Isto é feito observando o limite inferior de cada nó \cite{koerich}. Como o menor limite inferior está presente no nó 2, então este é selecionado como mais promissor e será expandido. A expansão deste nó é mostrada na Figura 3.

\begin{figure} [!h]
\centering
\includegraphics{branchandbound3}
\caption{Árvore de Busca - Níveis 0, 1 e 2}
\end{figure}

\begin{figure} [!h]
\centering
\includegraphics{branchandbound4}
\caption{Árvore de Busca - Solução}
\end{figure}

Dentre os 6 nós promissores não expandidos (1, 3, 4, 5, 6 e 7), seleciona-se o nó mais promissor, ou seja, o que possui menor limite inferior. Neste caso, trata-se do nó 5. A expansão deste nó é ilustrada na Figura 4.

Isto leva a uma solução possível: {\it {a-2, b-1, c-3, d-4}}. O custo desta solução é 13. Esta é uma solução viável e, como previsto, possui custo superior a 10, que era o custo mínimo possível para uma solução. Tendo sido encontrada uma solução viável, é preciso verificar os nós restantes, de modo a encontrar uma solução que tenha custo menor que 13.

Observando-se cada um dos nós promissores que ainda não foram expandidos, nenhum deles possui um limite inferior menor que 13. Isto significa que se expandíssemos cada um destes nós em busca de uma solução melhor que a atual, não iríamos localizá-la, pois o limite inferior já demonstra que não haveria solução de custo menor que o limite inferior de cada nó expandido. Com isto, estes nós podem ser podados sem a necessidade de expansão. A solução atual (viável) passa a ser a solução ótima e o algoritmo de {\it branch and bound} é encerrado, reduzindo assim o custo de execução do algoritmo e, logo, o custo de localização da solução ótima.

\section{Conclusão}

O {\it branch and bound} é um algoritmo genérico de otimização. Este algoritmo possui diversas versões, sendo que neste trabalho, foi explicado o funcionamento do {\it branch and bound} básico. As demais versões consistem em alguma versão anterior com uma ou mais estratégias acrescentadas ou substituídas \cite{roncatti}. Entre outras versões, podem ser citados o {\it branch and bound} ordenado, o {\it branch and bound} rápido, o {\it branch and bound} com previsão parcial e o {\it branch and bound} adaptativo. 


\bibliographystyle{abbrv}
\bibliography{refs}


\end{document}
